299. Сортировка поезда

На железнодорожной станции находится поезд, который состоит из n вагонов, пронумерованных от 1 до n. Разрешается менять местами только соседние вагоны. Необходимо найти наименьшее количество таких операций, за которое можно отсортировать все вагоны поезда.

Вход. Первая строка содержит количество тестов. Каждый тест состоит из двух строк: первая содержит количество вагонов в поезде L (0 £ L £ 50), а вторая – перестановку чисел от 1 до L, указывая текущий порядок вагонов.

Выход. Для каждого теста вывести минимальное количество перестановок соседних вагонов, которыми можно отсортировать вагоны поезда по возрастанию (первым идет вагон с номером 1, последним – вагон с номером L).

Пример входа	Пример выхода
3 3 1 3 2 4 4 3 2 1 2 2 1	Optimal train swapping takes 1 swaps. Optimal train swapping takes 6 swaps. Optimal train swapping takes 1 swaps.

РЕШЕНИЕ

сортировка

Анализ алгоритма

Пусть a₁, a₂, …, a_n – перестановка множества {1, 2, …, n}. Если i < j и a_i > a_j, то пара (a_i, a_j) образует инверсию. Минимальное количество перестановок соседних вагонов, необходимое для их сортировки, равно числу инверсий во входной перестановке.

Пример

Рассмотрим второй тест. Четверка образует три инверсии, тройка – две, двойка – одну. Итого 6 инверсий. Минимальное количество перестановок, за которое можно упорядочить числа по возрастанию, равно 6:

4 3 2 1 à 3 4 2 1 à 3 2 4 1 à 3 2 1 4 à

2 3 1 4 à 2 1 3 4 à 1 2 3 4

Реализация алгоритма

Читаем количество тестов. Для каждого теста заносим перестановку в массив m.

scanf("%d",&tests);

while(tests--)

{

scanf("%d",&n);

for(i = 0; i < n; i++)

scanf("%d",&m[i]);

В переменной res подсчитываем количество инверсий в исходной перестановке и выводим результат согласно требуемому формату.

res = 0;

for(i = 0; i < n - 1; i++)

for(j = i + 1; j < n; j++)

if (m[i] > m[j]) res++;

printf("Optimal train swapping takes %d swaps.\n",res);

}